
// 题干：给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。
//       你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

// 示例：输入：head = [1,2,3,4]
//       输出：[2,1,4,3]

// 碎语：整体思想，注意最后的退出是要返回head，即不倒置，直接返回节点指针

#include <bits/stdc++.h>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution
{
public:
    ListNode* swapPairs(ListNode* head)
    {
        if (head == nullptr || head->next == nullptr){
            return head;
        }

        auto next = head->next;
        head->next = next->next;
        next->next = head;
        head->next = swapPairs(head->next);

        return next;
    }
};

int main()
{
    Solution sol;
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);

    auto index = sol.swapPairs(head);
    while (index != nullptr){
        cout << index->val << " ";
        index = index->next;
    }

    return 0;
}